/*
 * nPuzzle.cpp
 *
 *  Created on: Sep 14, 2011
 *      Author:
 */

#include "puzzleSettings.h"
#include "search.cpp"
#include <ctime>
#include <sys/time.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

bool isSolvable(node & node_input);
void getBoard(puzzle & board, int which);
void getRandomBoard(puzzle & board);
void getBoardFile(node & node_input, char * param);
void getBoardCommand(node & node_input, char**);
double performRun(nodeBroker &);

void printStatistics(nodeBroker &, search &, double);


int main(int argc, char *argv[]) {

	//start timing of allocation of NodeBroker
	struct timeval start, stop, brokerStop;
    double seconds, useconds, brokerTime;
    gettimeofday(&start, NULL);
    nodeBroker broker;
    gettimeofday(&brokerStop, NULL);
    seconds  = brokerStop.tv_sec  - start.tv_sec;
    useconds = brokerStop.tv_usec - start.tv_usec;
    brokerTime = ((seconds) * 1000 + useconds/1000.0) + 0.5;


	//  if timing is turned on, no input is taken from file in arguments.
	if(stats && timing){
		double average = 0;
		for (int i = 0; i< 50; i++){
			double time = performRun(broker) + brokerTime;
			cout << "run " << i << " took " << time << " ms." << endl;
			if(time < 0)
				time = average;
			average = average * i;
			average += time;
			average /= (i + 1);
			cout << "updated average is " << average << endl;
			broker.reset();
		}
		return 0;
	}


	cout << "================================================================" << endl;
	cout << "====================    NEW BOARD   ============================" << endl;
	cout << "================================================================" << endl;
	//STEP 0: Initialize
	node * root = broker.newNode();

	/* process external file if given.
	 * Assumes that if there is an argument then the sole argument is the name of the file we are to read the board in from.
	 *
	 * PLEASE NOTE: if inputting from a board of a different size then the program has to be re-compiled and the size set in
	 * the puzzlesettings.h file.
	 */

	//STEP 0: GET INITIAL BOARD
	if(argc >1 ){
		if(argc != size +1){
			cout << "argc = " << argc << " size = " << size << endl;
			exit(-1);
		}
		//first argument is the file name.
		getBoardCommand(*root, argv);
	} else {
		getBoard(root->board,testBoard);
	}

	//start timer if taking stats.
	if(stats)
	    gettimeofday(&start, NULL);

	//set cost for root node.
	root->CostForChild(NULL);
	root->parent = NULL;


	//STEP 1: CHECK SOLVABLE
	if(!isSolvable(*root))
	{
		root->board.printBoard();
		cout << "Board Configuration is not Solvable." <<endl;
		return 0;
	}

	//STEP 2: INITIALIZE ALGORITHM
	//root->printNode();

	search Search;
	Search.begin(root, &broker, start);

	//solution was either found or not found and begin function took care of printing solution if it exists.

	if(stats){
	    gettimeofday(&stop, NULL);

	    seconds  = stop.tv_sec  - start.tv_sec;
	    useconds = stop.tv_usec - start.tv_usec;

	    double mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;

		printStatistics(broker, Search, mtime);
	}

	return 0;
}


/*
 * isSolvable(node)
 *
 * This function checks the board configuration for an even configuration and returns true if the board is even.
 *
 * The board property even is defined as follows:
 * for every tile, count the number of tiles less than it that have a higher position than this tile's current position.
 * Add these counts together for every tile and add to the sum the the position of the empty tile mod 2.
 */
bool isSolvable(node & node_input){
        int j =0, sum =0;
        for (int i = 0;i<size;i++){  //for each tile
            for(j=0 ; j<i ; j++){  //for every tile to the left of it.

                if((node_input.board).board[j] > (node_input.board.board[i]) ){  //if the tiles are out of place
                    sum = sum + 1;  //add 1 to the count.

                }
            }
        }

        /* Determine Parity.
         *
         * Even Board
         *
         * 0 1 0 1
         * 1 0 1 0
         *
         *
         * Odd Board
         *
         * 0 1 0
         * 1 0 1
         *
         */
        int row = node_input.board.emptyPos / width;
        int col = node_input.board.emptyPos % width;
        if(row % 2 == 0) //even row, 0 is even
        	sum = sum + col % 2; //even row then column oddness => parity = 1
        else
        	sum = sum + col % 2 + 1; //row oddness then column evenness ==> parity = 1;

        return sum%2 ==0;  //even sum is solvable.
    }


//imports board as list of tiles on command prompt.
void getBoardCommand(node & node_input, char * argV[]){
	//we are assuming that input matches size.
	for(pos spot = 0; spot < size; spot++){
		char * argument = argV[spot+1]; //skip leading program name
		pos tile = atoi(argument);
		node_input.board.board[spot] = tile;
		if(tile == 0)
			node_input.board.emptyPos = spot;
	}

}

//reads from given file in the param.
void getBoardFile(node & node_input, char * param){



        string line = "";
        ifstream myfile;
        myfile.open("input.txt");
        int i =0;
          if (myfile.is_open())
          {

            while ( myfile.good() )
            {

              getline (myfile,line);
              int tile = atoi(line.c_str());

              node_input.board.board[i] = tile;
              i++;
              if (tile == 0){
            		  node_input.board.emptyPos = (i-1);

              }
            }
            myfile.close();
          }

          else {
                  cout << "Unable to open file";
                  exit(-1);
          }

}




/*
 * prints the stats we collect through running the program.
 *
 */
void printStatistics(nodeBroker & broker, search &searchEngine, double time){
	cout << "================        STATISTICS          ====================" << endl;
    cout << "Elapsed time: " << time << " milliseconds" << endl;
	cout << "Pre Allocated Nodes: " << memSize << endl;
	cout << "Total Node Footprint: " << broker.memUsed << endl;
	cout << "Total Calls to New Node: " << broker.newNodeCalls << endl;
	cout << "Total Nodes Recycled: " << broker.nodesRecycled << endl;
	cout << "================================================================" << endl;
	cout << "================================================================" << endl;
	cout << "================================================================" << endl;
	cout << endl << endl << endl;
}



/**
 * RUNS
 */
double performRun(nodeBroker &broker){


	struct timeval start, stop;
    double seconds, useconds;

	//START TIMER IF TAKING STATS
    gettimeofday(&start, NULL);


		//STEP 0: Initialize
    	node * root = broker.newNode();



		//STEP 0: GET INITIAL BOARD
		getBoard(root->board,testBoard);
		//	getBoardFile(*root, argv[0]);

		root->cost_moves = 1;
		root->parent = NULL;


		root->CostForChild(NULL);



		//STEP 1: CHECK SOLVABLE
		if(!isSolvable(*root))
		{
			cout << "Board Configuration is not Solvable." <<endl;
			return -1;
		}

		//STEP 2: INITIALIZE ALGORITHM
		//root->printNode();

		search Search;
		Search.begin(root, &broker, start);

	    gettimeofday(&stop, NULL);

	    seconds  = stop.tv_sec  - start.tv_sec;
	    useconds = stop.tv_usec - start.tv_usec;

	   return ((seconds) * 1000 + useconds/1000.0) + 0.5;
	}


/**
 * Get Random Board
 *
 * Initialize all positions to 0, then write over the positions one at a time until only 0 is left.
 */

void getRandomBoard(puzzle & board){
	/* initialize random seed: */
	  srand ( time(NULL) );
	for(int i = 0; i < size; i ++)
		board.board[i] = 0;

	board.emptyPos = 0;

	for(int tile = size-1; tile > 0; tile--){ //for each tile.
		pos place = rand() % size;  //pick a place for the tile.
		while(board.board[place] != 0) //while placement is occupied
			place = (place + 1) % size; //advance to the next place, wrapping around the board.
		board.board[place] = tile; //set the tile in the empty spot.
	}
	// all but 1 empty spots are filled.  Find the empty position.

	for(int i = 0; i < size; i ++)
		if(board.board[i] == 0){
			board.emptyPos = i;
			return;
		}
}

//INPUT BOARD
void getBoard(puzzle & board, int which){
	switch(which){
	case 0: getRandomBoard(board); return;
	case 1: //boards are in worst case order.
		switch(width){
		case 3:
			board.board[0] = 8;
			board.board[1] = 7;
			board.board[2] = 6;
			board.board[3] = 5;
			board.board[4] = 4;
			board.board[5] = 3;
			board.board[6] = 2;
			board.board[7] = 1;
			board.board[8] = 0;
			board.emptyPos = 8;
			break;
		case 4:
			board.board[0] = 15;
			board.board[1] = 14;
			board.board[2] = 13;
			board.board[3] = 12;
			board.board[4] = 11;
			board.board[5] = 10;
			board.board[6] = 9;
			board.board[7] = 8;
			board.board[8] = 7;
			board.board[9] = 6;
			board.board[10] = 5;
			board.board[11] = 4;
			board.board[12] = 3;
			board.board[13] = 2;
			board.board[14] = 1;
			board.board[15] = 0;
			board.emptyPos = 15;
			break;
		case 5:
			board.board[0] = 24;
			board.board[1] = 23;
			board.board[2] = 22;
			board.board[3] = 21;
			board.board[4] = 20;
			board.board[5] = 19;
			board.board[6] = 18;
			board.board[7] = 17;
			board.board[8] = 16;
			board.board[9] = 15;
			board.board[10] = 14;
			board.board[11] = 13;
			board.board[12] = 12;
			board.board[13] = 11;
			board.board[14] = 10;
			board.board[15] = 9;
			board.board[16] = 8;
			board.board[17] = 7;
			board.board[18] = 6;
			board.board[19] = 5;
			board.board[20] = 4;
			board.board[21] = 3;
			board.board[22] = 2;
			board.board[23] = 1;
			board.board[24] = 0;
			board.emptyPos = 24;
			break;
		case 6:
			board.board[0] = 35;
			board.board[1] = 34;
			board.board[2] = 33;
			board.board[3] = 32;
			board.board[4] = 31;
			board.board[5] = 30;
			board.board[6] = 29;
			board.board[7] = 28;
			board.board[8] = 27;
			board.board[9] = 26;
			board.board[10] = 25;
			board.board[11] = 24;
			board.board[12] = 23;
			board.board[13] = 22;
			board.board[14] = 21;
			board.board[15] = 20;
			board.board[16] = 19;
			board.board[17] = 18;
			board.board[18] = 17;
			board.board[19] = 16;
			board.board[20] = 15;
			board.board[21] = 14;
			board.board[22] = 13;
			board.board[23] = 12;
			board.board[24] = 11;
			board.board[25] = 10;
			board.board[26] = 9;
			board.board[27] = 8;
			board.board[28] = 7;
			board.board[29] = 6;
			board.board[30] = 5;
			board.board[31] = 4;
			board.board[32] = 3;
			board.board[33] = 2;
			board.board[34] = 1;
			board.board[35] = 0;
			board.emptyPos = 35;
			break;


		}
		break;
	case 2:  //board is half way out of order.
		switch(width){
		case 3:
			board.board[0] = 7;
			board.board[1] = 6;
			board.board[2] = 5;
			board.board[3] = 3;
			board.board[4] = 0;
			board.board[5] = 1;
			board.board[6] = 8;
			board.board[7] = 4;
			board.board[8] = 2;
			board.emptyPos = 4;
			break;
		case 4:
			board.board[0] = 15;
			board.board[1] = 14;
			board.board[2] = 12;
			board.board[3] = 13;
			board.board[4] = 11;
			board.board[5] = 10;
			board.board[6] = 0;
			board.board[7] = 1;
			board.board[8] = 2;
			board.board[9] = 3;
			board.board[10] = 5;
			board.board[11] = 4;
			board.board[12] = 6;
			board.board[13] = 9;
			board.board[14] = 7;
			board.board[15] = 8;
			board.emptyPos = 6;
			break;
		case 5:
			board.board[0] = 24;
			board.board[1] = 23;
			board.board[2] = 22;
			board.board[3] = 21;
			board.board[4] = 20;
			board.board[5] = 19;
			board.board[6] = 18;
			board.board[7] = 17;
			board.board[8] = 16;
			board.board[9] = 15;
			board.board[10] = 14;
			board.board[11] = 13;
			board.board[12] = 0;
			board.board[13] = 1;
			board.board[14] = 2;
			board.board[15] = 3;
			board.board[16] = 4;
			board.board[17] = 5;
			board.board[18] = 6;
			board.board[19] = 7;
			board.board[20] = 8;
			board.board[21] = 9;
			board.board[22] = 10;
			board.board[23] = 11;
			board.board[24] = 12;
			board.emptyPos = 12;
			break;
		}
		break;
		case 3:
			switch(width){
			case 3:
				board.board[0] = 7;
				board.board[1] = 2;
				board.board[2] = 1;
				board.board[3] = 5;
				board.board[4] = 4;
				board.board[5] = 0;
				board.board[6] = 6;
				board.board[7] = 8;
				board.board[8] = 3;
				board.emptyPos = 5;
				break;
			case 4:
				board.board[0] = 7;
				board.board[1] = 6;
				board.board[2] = 5;
				board.board[3] = 4;
				board.board[4] = 3;
				board.board[5] = 2;
				board.board[6] = 1;
				board.board[7] = 0;
				board.board[8] = 15;
				board.board[9] = 14;
				board.board[10] = 13;
				board.board[11] = 12;
				board.board[12] = 11;
				board.board[13] = 10;
				board.board[14] = 9;
				board.board[15] = 8;
				board.emptyPos = 7;
				break;
			}
			break;
			case 4:  // NO MOVES NECESSARY
				switch(width){
				case 3:
					board.board[0] = 0;
					board.board[1] = 1;
					board.board[2] = 2;
					board.board[3] = 3;
					board.board[4] = 4;
					board.board[5] = 5;
					board.board[6] = 6;
					board.board[7] = 7;
					board.board[8] = 8;
					board.emptyPos = 0;
					break;
				case 4:
					board.board[0] = 0;
					board.board[1] = 1;
					board.board[2] = 2;
					board.board[3] = 3;
					board.board[4] = 4;
					board.board[5] = 5;
					board.board[6] = 6;
					board.board[7] = 7;
					board.board[8] = 8;
					board.board[9] = 9;
					board.board[10] = 10;
					board.board[11] = 11;
					board.board[12] = 12;
					board.board[13] = 13;
					board.board[14] = 14;
					board.board[15] = 15;
					board.emptyPos = 0;
					break;
				}
				break;
				case 5:  // 2 tiles swapped
					switch(width){
					case 3:
						board.board[0] = 0;
						board.board[1] = 2;
						board.board[2] = 1;
						board.board[3] = 3;
						board.board[4] = 4;
						board.board[5] = 6;
						board.board[6] = 5;
						board.board[7] = 7;
						board.board[8] = 8;
						board.emptyPos = 0;
						break;
					case 4:
						board.board[0] = 0;
						board.board[1] = 2;
						board.board[2] = 1;
						board.board[3] = 3;
						board.board[4] = 4;
						board.board[5] = 6;
						board.board[6] = 5;
						board.board[7] = 7;
						board.board[8] = 8;
						board.board[9] = 9;
						board.board[10] = 10;
						board.board[11] = 11;
						board.board[12] = 12;
						board.board[13] = 13;
						board.board[14] = 14;
						board.board[15] = 15;
						board.emptyPos = 0;
						break;
					}
					break;

					case 6:  // prof given board
						switch(width){
						case 3:
							board.board[0] = 2;
							board.board[1] = 4;
							board.board[2] = 8;
							board.board[3] = 1;
							board.board[4] = 6;
							board.board[5] = 5;
							board.board[6] = 0;
							board.board[7] = 7;
							board.board[8] = 3;
							board.emptyPos = 6;
							break;
						case 4:
							board.board[0] = 1;
							board.board[1] = 3;
							board.board[2] = 4;
							board.board[3] = 8;
							board.board[4] = 5;
							board.board[5] = 2;
							board.board[6] = 0;
							board.board[7] = 7;
							board.board[8] = 9;
							board.board[9] = 6;
							board.board[10] = 10;
							board.board[11] = 11;
							board.board[12] = 13;
							board.board[13] = 14;
							board.board[14] = 12;
							board.board[15] = 15;
							board.emptyPos = 6;
							break;
						}
						break;
	}
}

